package com.cat.dataStructure02;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/description/
 * @create 2025/11/2 16:02
 * @since JDK17
 */

public class Solution97 {
    int n, m;
    static int[][] dire = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    List<Integer> toList(int[][]mat) {
        return Arrays.stream(mat).flatMapToInt(Arrays::stream).boxed().collect(Collectors.toList());
    }
    void toArray(int[][]mat, List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            mat[i / m][i % m] = list.get(i);
        }
    }
    boolean check(int[][] mat) {
        return Arrays.stream(mat).flatMapToInt(Arrays::stream).sum() == 0;
    }
    void chang(int[][] mat, int i, int j) {
        mat[i][j] = 1 - mat[i][j];
        for (int[] d : dire) {
            int x = i + d[0], y = j + d[1];
            if (x < 0 || x >= n || y < 0 || y >= m) {
                continue;
            }
            mat[x][y] = 1 - mat[x][y];
        }
    }

    public int minFlips(int[][] mat) {
        n = mat.length;
        m = mat[0].length;
        Set<List<Integer>> set = new HashSet<>();
        List<List<Integer>> q = new ArrayList<>();
        q.add(toList(mat));
        set.add(q.get(0));
        int ans = 0;
        while (!q.isEmpty()) {  //
            var t = new ArrayList<>(q);
            q = new ArrayList<>();
            for (int i = 0; i < t.size(); i++) {
                toArray(mat, t.get(i));
                if (check(mat)) {   // 全部都清零了
                    return ans;
                }
                for (int r = 0; r < n; r++) {   // 每个位置开是枚举
                    for (int c = 0; c < m; c++) {
                        chang(mat, r, c);
                        var l = toList(mat);
                        if (set.add(l)) {   // 这个状态之前没有出现过
                            // System.out.println(r + " " + c);
                            q.add(l);
                        }
                        chang(mat, r, c);
                    }
                }
            }
            ans++;
        }
        return -1;
    }
}
